长大后想做什么？做回小孩！

0%

LeetCode——岛屿的最大面积

发表于 更新于 分类于 Valine：
本文字数： 414

NO.695 岛屿的最大面积 中等

81gBKe.png

思路一：广度优先遍历 这道题给我的第一感觉和腐烂的橘子那道题很像，都是多源向外”辐射”寻找。

用一个和grid大小一样的boolean型数组used标识每个位置是否用过，max统计最大岛屿面积。

遍历矩阵，如果当前位置是陆地(1)并且没有被使用过，就从当前位置进行广搜最后更新最大岛屿面积；否则继续遍历。

简陋的BFS模板：

1
2
3
4
5
6
7
8
while(队列不空){
	node=队列.poll();
	for(node的邻接节点){
		if(邻接节点m未曾入队){
			队列.add(m);
		}
	}
}

很明显这是个模板题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
boolean[][] used;
int m;
int n;
public int maxAreaOfIsland(int[][] grid) {
    int max=0;
    this.m=grid.length;
    this.n=grid[0].length;
    this.used=new boolean[m][n];
    //遍历每个位置
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            //如果是陆地且没用过
            if (grid[i][j]==1&&!used[i][j]){
                //广搜更新最大岛屿面积
                max=Math.max(max,bfs(grid,i,j));
            }
        }
    }
    return max;
}
//广搜
private int bfs(int[][] grid, int i, int j) {
    //广搜队列
    Queue<int[]> queue=new LinkedList<>();
    queue.add(new int[]{i,j});//当前陆地入队
    used[i][j]=true;//更新标记数组
    int res=1;//开始就是一块陆地
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int r=curr[0],c=curr[1];
        //判断当前出队陆地的上下左右是否是陆地且没使用过
        if (r-1>=0&&grid[r-1][c]==1&&!used[r-1][c]){
            queue.add(new int[]{r-1,c});
            used[r-1][c]=true;
            res++;
        }
        if (c-1>=0&&grid[r][c-1]==1&&!used[r][c-1]){
            queue.add(new int[]{r,c-1});
            used[r][c-1]=true;
            res++;
        }
        if (r+1<m&&grid[r+1][c]==1&&!used[r+1][c]){
            queue.add(new int[]{r+1,c});
            used[r+1][c]=true;
            res++;
        }
        if (c+1<n&&grid[r][c+1]==1&&!used[r][c+1]){
            queue.add(new int[]{r,c+1});
            used[r][c+1]=true;
            res++;
        }
    }
    return res;
}

时间复杂度：O(m*n)

使用的这个used数组可以省略，每个使用过的陆地(1)直接置为0就可以了，我看很多人很形象地把这个叫做”沉岛思想”。用这种方式可以自行改进上一题，减少空间使用。

思路二：深度优先遍历 虽然改用深度优先遍历，实际上和上文思路一样，应该叫做实现二。

依然是遍历判断是否为1，如果是则采用深搜统计并更新max。

尝试抛弃used数组，改为”沉岛思想”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int maxAreaOfIsland(int[][] grid) {
    int max=0;
    //遍历
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            //是陆地
            if (grid[i][j]==1){
                //深搜并更新max
                max=Math.max(max,dfs(grid,i,j));
            }
        }
    }
    return max;
}
//深搜
private int dfs(int[][] grid, int i, int j) {
    //越界都是海水
    if (i<0||i==grid.length||j<0||j==grid[i].length){
        return 0;
    }
    if (grid[i][j]==1){
        grid[i][j]=0;//沉岛
        //上下左右四个方向深搜，别忘了开始的一块陆地
        return 1+dfs(grid,i+1,j)+dfs(grid,i-1,j)+dfs(grid,i,j+1)+dfs(grid,i,j-1);
    }
    return 0;
}

时间复杂度：O(m*n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github